单词检查(Ⅰ)

#单词检查(Ⅰ)| 来源: 网络整理| 查看: 265

题目描述许多应用程序，如字处理软件，邮件客户端等，都包含了单词检查特性。单词检查是根据字典，找出输入文本中拼错的单词，我们认为凡是不出现在字典中的单词都是错误单词。不仅如此，一些检查程序还能给出类似拼错单词的修改建议单词。例如字典由下面几个单词组成： bake cake main rain vase 如果输入文件中有词vake ，检查程序就能发现其是一个错误的单词，并且给出 bake, cake或vase做为修改建议单词。修改建议单词可以采用如下生成技术： (1)在每一个可能位置插入‘a-‘z’中的一者 (2)删除单词中的一个字符 (3)用‘a’-'z’中的一者取代单词中的任一字符很明显拼写检查程序的核心操作是在字典中查找某个单词，如果字典很大，性能无疑是非常关键的。你写的程序要求读入字典文件，然后对一个输入文件的单词进行检查，列出其中的错误单词并给出修改建议。

课程设计必须采用如下技术完成并进行复杂度分析及性能比较。 (1)朴素的算法,用线性表维护字典 (2)使用二叉排序树维护字典 (3)采用hash技术维护字典

本题要求使用顺序表实现。

输入输入分为两部分。第一部分是字典，每个单词占据一行，最后以仅包含’#'的一行表示结束。所有的单词都是不同的，字典中最多10000个单词。

输入的第二部分包含了所有待检测的单词，单词数目不超过50。每个单词占据一行，最后以仅包含’#'的一行表示结束。

字典中的单词和待检测的单词均由小写字母组成，并且单词最大长度为15。输出按照检查次序每个单词输出一行，该行首先输出单词自身。如果单词在字典中出现，接着输出" is correct"。如果单词是错误的，那么接着输出’:’，如果字典中有建议修改单词，则按照字典中出现的先后次序输出所有的建议修改单词（每个前面都添加一个空格），如果无建议修改单词，在’:'后直接换行。样例输入 Copy i is has have be my more contest me too if award

me aware m contest hav oo or i fi mre

样例输出 Copy me is correct aware: award m: i my me contest is correct hav: has have oo: too or: i is correct fi: i mre: more me

#include #include//C++调用字符串函数 using namespace std; #define MAXSIZE 10001//顺序表可能达到的最大长度 typedef char ElemType; typedef struct List{ ElemType elem[MAXSIZE]; int length; }SqList; SqList L[MAXSIZE];//全局变量，用于保存字典内容 int n=0;//用于统计输入字典单词个数 void protect(SqList S) { int i,flag=0; for(i=0;i//与字典一样 cout if(S.length-L[i].length==1){//输入比字典多一个字母 int count=0;//统计字母不相同的个数 for(int j=0,k=0;L[i].elem[j]!='\0';j++,k++){//逐个字母比较 if(L[i].elem[j]!=S.elem[k]){ count++; j--;//比较输入字符后面的字母 } if(count>=2) break;//没有可以修改的字典单词 } if(count//逐个字母比较 if(L[i].elem[j]!=S.elem[k]){ count++; k--;//比较字典字符后面的字母 } if(count>=2) break;//没有可以修改的字典单词 } if(count//逐个字母比较 if(L[i].elem[j]!=S.elem[k]){ count++; } if(count>=2) break;//没有可以修改的字典单词 } if(count if(L[n].elem[0]=='#') break;//输入字典完毕 L[n].length=strlen(L[n].elem); n++; } SqList S; while(cin>>S.elem){ if(S.elem[0]=='#') break; S.length=strlen(S.elem); protect(S); } }

【本文地址】

公司简介

联系我们